package 字符串匹配算法;

public class BM {

    private static final int SIZE = 256;

    public static void main(String[] args) {
        String str = "-300";
        double v = Double.parseDouble(str);
        if (v < 0){
            System.out.println("aaaa");
        }
        System.out.println(v);
    }


    public static int bm(String a,String b){
        return bm(a.toCharArray(),a.length() , b.toCharArray(),b.length() );
    }
    public static int bm(char[] a,int n,char[] b, int m){
        int[] bc = new int[SIZE];
        generateBC(b, m, bc);
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        generateGS(b,m ,suffix ,prefix );
        int i = 0; //表示主串,与模式串第一个字符对齐的位置
        while (i <= n - m){
            int j;
            //查找坏字符,j是坏字符在主串的位置
            for (j = i + m -1;j >= i;j--){
                if (b[j - i] != a[j]){
                    break;
                }
            }
            if (j < i ){
                //代表匹配成功
                return i;
            }
            //坏字符方法移动的距离
            int x = j -i - bc[(int) a[j]];
            int y = 0;
            if (j < m + i -1){
                //好后缀移动的距离
                y = moveGoodSuffix(j -i, m, suffix, prefix);
            }
            i += Math.max(x,y );
        }
        return -1;
    }




    public static void generateBC(char[] b,int m, int[] bc){
        //初始化bc
        for (int i = 0; i < SIZE; i++) {
            //-1代表模式串没有这个字符
            bc[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            bc[((int) b[i])] = i;
        }
    }

    public static void generateGS(char[] b,int m, int[] suffix,boolean[] prefix){
        for (int i = 0; i < m; i++) {
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m - 1; i++) {
            int j = i;
            int k = 0;
            while (j >= 0 && b[j] == b[m - 1 - k]){
                k++;
                suffix[k] = j;
                j--;
            }
            if (j == -1){
                prefix[k] = true;
            }
        }
    }


    //好后缀规则
    public static int moveGoodSuffix(int bci,int m,int[] suffix,boolean[] prefix){
        int j;
        //先判断整个是不是好后缀
        if ((j = suffix[m - bci - 1]) != -1){
            return bci - j + 1;
        }
        //
        for (int i = bci + 2; i < m - 1; i++) {
            if (prefix[m - i]){
                return i;
            }
        }
        return m;
    }
}
